package niuke;

import java.util.ArrayList;
import java.util.Arrays;

/**
 * description:
 * author:zt
 * date:2021-08-02
 */

/**
 * 含重复字符的全排列
 */
public class NC121 {
    ArrayList<String> res = new ArrayList<>();
    StringBuilder sb = new StringBuilder();
    boolean[] flag;
    public ArrayList<String> Permutation(String str) {
        char[] c = str.toCharArray();
        flag = new boolean[c.length];
        Arrays.sort(c);

        dfs(c,0,c.length);
        return res;
    }
    public void dfs(char[] c,int depth,int len){
        if (depth==len) res.add(sb.toString());
        for (int i = 0; i < len; i++) {
            if (i>0 && c[i]==c[i-1] && !flag[i-1]) continue;
            if (!flag[i]){
                sb.append(c[i]);
                flag[i] = true;
                dfs(c,depth+1,len);
                sb.deleteCharAt(sb.length()-1);
                flag[i] = false;
            }
        }
    }
}
